﻿namespace Leetcode.N0015;


public class Solution
{
    public IList<IList<int>> ThreeSum(int[] nums)
    {
        nums = nums.OrderBy(i => i).ToArray();
        var dic = new Dictionary<int, ISet<int>>();

        for (int i = 0; i < nums.Length; i++)
        {
            if (!dic.ContainsKey(nums[i]))
            {
                dic.Add(nums[i], new HashSet<int>() { i });
            }
            else
            {
                dic[nums[i]].Add(i);
            }
        }

        var result = new List<IList<int>>();
        var hashSet = new HashSet<long>();

        for (int i = 0; i < nums.Length; i++)
        {
            if (i > 0 && nums[i] == nums[i - 1])
            {
                continue;
            }

            for (int j = i + 1; j < nums.Length; j++)
            {
                if (j > i + 1 && nums[j] == nums[j - 1])
                {
                    continue;
                }

                var val = nums[i] + nums[j];
                if (!dic.ContainsKey(-val))
                {
                    continue;
                }
                var find = dic[-val];
                if (find.Count == 1 && (find.Contains(i) || find.Contains(j))
                   || find.Count == 2 && nums[i] == 0 && nums[j] == 0)
                {
                    continue;
                }
                var item = (new int[] { nums[i], nums[j], -val }).OrderBy(k => k).ToList();
                var key = ((long)100000 - item[0]) * 1000000000000 + ((long)item[1] < 0 ? 100000 - item[1] : item[1]) * 1000000 + item[2];
                if (hashSet.Add(key))
                {
                    result.Add(item);
                }
            }
        }
        return result;
    }
}